1. Technical Field
The invention is related to a system for “downsampling” signals for which a transformed representation via a hierarchical transform is available, and in particular, to a system and method for rendering reduced resolution signals by operating on the hierarchical transformed representation of a signal in the transform domain using space-variant filters aligned to the blocks used in the hierarchical transform.
2. Background Art
Downsampling of signals of various dimensionality, such as, for example audio signals, images or video signals, biomedical data, economic time series data, etc., is a concept that is well known to those skilled in the art. In general, downsampling a signal operates to render or otherwise produce a reduced resolution version of the signal.
For example, an image displayed on the LCD on the back of a conventional digital still or video camera is typically a reduced resolution version of an image that has been captured by that camera. There are many such uses for signal downsampling, such as for use in simply fitting a signal, such as image, into an available display space or an available memory space, by generating reduced resolution versions of such signals. For example, if an original image captured by a digital camera has dimensions 1,792×1,200 pixels (e.g. from a 2-megapixel digital camera), it may be desired to quickly generate good-quality renditions of the image at various resolutions, such as, for example 896×600 (2:1 downsampling), 448×300 (4:1 downsampling), 224×150 (8:1 downsampling), or 112×75 (16:1 downsampling). Such reduced-resolution images are useful for picture previewing, displaying in small screens, or for displaying groups of pictures, or “thumbnail” representations of the pictures, in a single display window.
There are many well known techniques for downsampling signals. For example, with respect to images, one popular method involves separable downsampling (using the same filters in the horizontal and vertical directions), and using symmetric filter kernels that provide a good compromise between sharpness and aliasing artifacts. Typical filters used for image downsampling include averaging, bilinear, and bicubic filters.
In general, the common approach to signal downsampling of an encoded signal is to first decode the full-resolution signal, and then generate the reduced resolution version using conventional downsampling techniques. For example, to generate a 112×75 pixel version of a 1,792×1,200 encoded image, many conventional downsampling techniques will first decode the entire 1,792×1,200 encoded image, and then generate the 112×75 version of the image using four steps of bicubic downsampling. Downsampling of other types of encoded signals uses similar techniques.
Consequently, one problem with such conventional downsampling techniques is that producing downsampled versions of a signal tends to be computationally expensive, and is therefore relatively slow. This problem is especially evident when generating significantly downsampled versions of the signal. Further, as is well known to those skilled in the art, another problem which frequently results from downsampling of signals involves a degradation of the signal, which may include the introduction of artifacts into the signal, depending upon the types of filters used in downsampling the signal.
As is well known to those skilled in the art, a hierarchical transforms (HT), also known as generalized hierarchical transform is a transform operator that maps a signal (of any desired dimensionality) to transform coefficients at different levels of resolution, depending upon the type of transform used. Various types of hierarchical transforms include, for example, wavelet-based transforms (WT) and lapped transforms, such as, for example, the lapped biorthogonal transform (LBT).
For example, many conventional compression algorithms employ a wavelet transform (WT) followed by quantization and entropy encoding to provide for hierarchical encoding of such signals. One useful feature of using WTs is that WT-based codecs naturally allow for image reconstruction that is progressive in resolution, typically at resolution factors of 2 (e.g., 1:1, 2:1, 4:1, 8:1, etc.). In fact, codecs based on the well-known JPEG-2000 standard are implemented using wavelet transforms. However, one disadvantage to using codecs based on WTs, is that in many cases, such codecs are less computationally efficient, and typically require a larger memory footprint, than other hierarchical transforms such as codecs implemented using LBTs. Further, because there are more hierarchical encoding levels using wavelets such as those described above, there is an additional likelihood of aliasing or other artifacts appearing in the various hierarchically encoded levels of the signal relative to LBT-based codecs.
In general, as is well known to those skilled in the art, LBTs take an input signal, and divide that signal into blocks of N samples, which are then transformed by a core transform operator that maps N signal samples into N transform coefficients. Then, for each block, L coefficients are brought to the next level of transformation and grouped by a frequency index. For each succeeding resolution level, this process is simply repeated. Since for each block, only L of N coefficients are brought to the next level, the signal length is reduced by a factor N/L at every transform stage.
Unfortunately, conventional hierarchical codecs using LBT's typically use N=4 (or larger) and L=1, so that only the lowest-frequency (usually called DC) coefficient is brought to the next level. As a result, in this example, resolution at each hierarchical level is reduced by a factor of N/L=4 in each signal dimension, at each level. Consequently, in order to render intermediate resolution levels other than those specifically encoded (e.g., 1:1, 4:1, 16:1, 64:1, 256:1, etc.) conventional downsampling techniques are again used, as described above. In particular, with conventional LBT-based HT schemes, the signal is then decoded to the resolution level immediately above the desired resolution level, and then the decoded signal is downsampled to the desired level using conventional downsampling techniques (such as bicubic lowpass filtering of images). Again, such downsampling techniques in the signal domain tend to be computationally expensive, and may introduce distortions or other artifacts into the signal.
Therefore, what is needed is a system and method for providing reduced resolution versions of a hierarchical transform representation of a signal while minimizing or eliminating the need to directly downsample higher resolution versions of the signal, depending upon the desired resolution level. As a result, signal degradation resulting from multiple levels of downsampling is reduced or eliminated. Further, such a system and method should operate to reduce the computational overhead necessary to generate such reduced resolution versions of the signal.